package com.heima.leetcode.practice;

import java.util.LinkedList;

/**
 * leetcode 42 接雨水
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/18 19:51
 */
public class E42 {

    /**
     * <h3>方法一：单调栈，雨水拆分是以横向拆分的</h3>
     *
     * @param height 柱子高度数组
     * @return 接雨水量
     */
    public int trap1(int[] height) {
        LinkedList<Pillar> stack = new LinkedList<>();
        int water = 0;
        for (int i = 0; i < height.length; i++) {
            int currHeight = height[i];
            while (!stack.isEmpty() && currHeight > stack.peek().height) {
                Pillar pop = stack.pop();
                if (stack.isEmpty()) break;
                Pillar peek = stack.peek();
                int h = Math.min(currHeight - pop.height, peek.height - pop.height);
                water += h * (i - peek.index - 1);
            }
            stack.push(new Pillar(i, currHeight));
        }
        return water;
    }

    /**
     * 柱子类
     */
    static class Pillar {
        int index;
        int height;

        public Pillar(int index, int height) {
            this.index = index;
            this.height = height;
        }
    }

    /**
     * <h3>方法二：双指针法，雨水拆分是以纵向拆分的</h3>
     *
     * @param height 柱子高度数组
     * @return 接雨水量
     */
    public int trap2(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, water = 0; // 记录当前遍历到的left柱子中的最大高度和right柱子中的最大高度
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (leftMax < rightMax) { // 小于等于都行，左边低右边高，所以左边可以接雨水
                // 左边柱子高度小于右边柱子高度，说明左边的柱子可以接雨水
                water += leftMax - height[left];
                left++;
            } else { // 右边低左边高，所以右边可以接雨水，等于的时候随便哪边都可以，本质是纵向拆分
                // 右边柱子高度小于左边柱子高度，说明右边的柱子可以接雨水
                water += rightMax - height[right];
                right--;
            }
        }
        return water;
    }
}
